package eashrine;

import java.util.Arrays;

/**
 * @Author: Siantar
 * @Date: 2023-06-24-14:08
 * @Description: 1.0
 */
public class T1659 {

    int n, m, tot;
    int[][] maskBits;
    int[] ivCount;
    int[] evCount;
    int[] innerScore;
    int[][] interScore;
    int[][][][] d;
    static int[][] score = {
            {0, 0, 0},
            {0, -60, -10},
            {0, -10, 40}
    };

    public int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
        this.m = m;
        this.n = n;
        this.tot = (int) Math.pow(3, n);
        this.maskBits = new int[tot][n];
        this.ivCount = new int[tot];
        this.evCount = new int[tot];
        this.innerScore = new int[tot];
        this.interScore = new int[tot][tot];
        this.d = new int[m][tot][introvertsCount + 1][extrovertsCount + 1];
        initData();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < tot; j++) {
                for (int k = 0; k < introvertsCount + 1; k++) {
                    Arrays.fill(d[i][j][k], -1);
                }
            }
        }
        System.out.println(1);
        return dfs(0, 0, introvertsCount, extrovertsCount);
    }

    public void initData() {
        for (int mask = 0; mask < tot; mask++) {
            int maskTmp = mask;
            for (int i = 0; i < n; i++) {
                int x = maskTmp % 3;
                maskBits[mask][i] = x;
                maskTmp /= 3;
                if (x == 1) {
                    ivCount[mask]++;
                    innerScore[mask] += 140;
                } else if (x == 2) {
                    evCount[mask]++;
                    innerScore[mask] += 40;
                }
                if (i > 0) {
                    innerScore[mask] += score[x][maskBits[mask][i - 1]];
                }
            }
        }
        for (int mask1 = 0; mask1 < tot; mask1++) {
            for (int mask2 = 0; mask2 < tot; mask2++) {
                interScore[mask1][mask2] = 0;
                for (int i = 0; i < n; i++) {
                    interScore[mask1][mask2] += score[maskBits[mask1][i]][maskBits[mask2][i]];
                }
            }
        }
    }

    public int dfs(int row, int preMask, int iv, int ev) {
        if (row == m || iv == 0 && ev == 0) {
            return 0;
        }

        if (d[row][preMask][iv][ev] != -1) {
            return d[row][preMask][iv][ev];
        }

        int res = 0;
        for (int mask = 0; mask < tot; mask++) {
            if (ivCount[mask] > iv || evCount[mask] > ev) {
                continue;
            }
            res = Math.max(res, dfs(row + 1, mask, iv - ivCount[mask], ev - evCount[mask])
                    + innerScore[mask] + interScore[mask][preMask]);
        }
        d[row][preMask][iv][ev] = res;
        return res;
    }


}
